Data storage media, such as hard disks, sometimes have errors due to write failures, physical damage to data storage media, deterioration of components of the storage media or other reasons. Some of these errors may remain latent until a particular portion of a data storage medium is accessed. To detect such storage media errors, a verification or “scrubbing” process may be employed to proactively verifies the integrity of stored data, for example, as a background process and/or on a periodic basis. Timely detection of such errors is often desirable, for example, to reduce the likelihood that correctable errors will accumulate into uncorrectable errors. However, with increasing capacity of data storage devices, it may take a long time to verify all data stored on a data storage device. Further, frequent data verification may impose system overhead such as interference with input/output (I/O) bandwidth, wear and tear to data storage devices and the like.